Computer programs are typically composed of a number of procedures, each of which may be called upon to perform a certain function, or process certain data, upon execution of the computer program. In conventional programming languages, procedures called when the computer program executes may each be represented by a "stack frame" in a defined region of a program's address space, the defined region being termed the "stack region".
Referring to FIG. 1, there is shown a schematic representation of a stack region 10 defined in a program's address space. The stack region 10 accommodates a call stack comprising N stack frames 12, each stack frame 12 representing and including data concerning a specific called procedure. A stack frame 12 is created and placed in the call stack when an associated procedure is called, and then removed (or "popped") from the call stack when the procedure is exited. Accordingly, the call stack represents a structure of nested procedures which are extant within a computer system at any given moment. For example, in the situation illustrated in FIG. 1, the procedure associated with stack frame (N-1) would have called the procedure associated with stack frame (N).
Each stack frame 12 may include a frame marker 14, an activation record 16, and saved registers 18. The frame marker 14 is located at the top of the stack frame 12, and may include "bookkeeping" information, such as a pointer to the immediately preceding stack frame (i.e. a Previous Stack Pointer (PSP)) and a pointer to the return point in the calling procedure (i.e. a Return Pointer (RP)). The activation record 16 includes information concerning the local state that must be stored in memory by the associated procedure, including local variables and tempories. Each stack frame 12 also includes space to save registers that must be saved across procedure calls.
Stack unwinding is the process of tracing backwards through the activation records contained in a call stack. Debuggers and exception handling mechanisms require the ability to "unwind" the call stack, or trace back through a series of stack frames, from the stack frame for the most recently called procedure to that for the outermost procedure of a program. For example, a debugger may need to unwind the call stack to print a stack trace, while an exception handling mechanism may need to remove a number of stack frames from the call stack, and to transfer control to an exception handling routine which is located down the stack. As the stack is unwound, values of preserved registers, saved by each procedure, are recovered so as to allow the debugger or exception handler access to correct values for local variables.
Complex Instruction Set Computing (CISC) and Reduced Instruction Set Computing (RISC) architectures have fundamentally differing approaches to stack frames. CISC architectures typically provide special instruction-set support for the stack mechanism, with a single instruction to allocate a stack frame and to create a frame marker when a procedure is called, and another single instruction to return from a procedure call and to remove the relevant stack frame from the call stack.
The advent of RISC architectures allowed the allocation, creation, return and removal steps to be divided into a number of higher resolution sub-operations, which can be eliminated when unnecessary. For example, where it is known that the size of the stack frame is not varied by the associated procedure, there is no need to save the Previous Stack Pointer (PSP), and both save and retrieve operations with respect to the PSP can be eliminated.
However, in RISC architecture environments, the debugger may now need additional information to perform a stack unwind operation in view of the non-uniform content and formats of stack frames. For example, for any given stack frame, a PSP may or may not be included in the relevant frame marker. If the PSP is saved, the debugger can immediately locate the previous stack frame; if not, the debugger needs to determine the size of the stack frame and then calculate the location of the preceding stack frame. An exception handler may also require additional information regarding what registers have been saved in a stack frame, and when and where these registers were saved.
In order provide this additional information required in RISC architectures, a stack unwind table may be generated by a compiler. Such a stack unwind table includes static information that is required for unwinding the stack. It is desirable that a stack unwind table be as compact as possible, and also facilitate optimization techniques to be applied to procedure code without compromising the ability to unwind the stack.